package com.problem.leetcode;

/**
 * 解题思路:
 * 1.首先想到的是排序，但是算法时间复杂度要求是o(n),所以剩下的排序算法就是计数排序法，但是计数排序法的空间复杂度是
 * o(n)，其实不需要整个数组有序即可求解，遍历第一次将数字放在正确的索引上，只关心正数即可，第二次遍历找出数字和索引不匹配的索引，即结果
 * 不过要小心有很多边界提爱条件
 *
 * @author didi
 * @DESCRIPTION
 * @create 2019-04-22 13:35
 **/

public class Problem41 {
    public int firstMissingPositive(int[] nums) {

        for (int index = 0; index < nums.length; ) {
            if (nums[index] > 0 && nums[index] < nums.length && nums[index] != index + 1 &&
                nums[nums[index] - 1] != nums[index]) {
                switchElement(nums, index, nums[index] - 1);
            } else {
                ++index;
            }
        }

        int result = -1;
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] != index + 1) {
                result = index;
                break;
            }
        }

        return result >= 0 ? result + 1 : nums.length + 1;
    }

    private void switchElement(int[] nums, int begin, int end) {
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
    }

    public static void main(String[] args) {
        // int result = new Problem41().firstMissingPositive(new int[]{-1, 4, 2, 1, 9, 10});
        // int result = new Problem41().firstMissingPositive(new int[]{1, 2, 0});
        // int result = new Problem41().firstMissingPositive(new int[]{-1,-2,-3,1});
        // int result = new Problem41().firstMissingPositive(new int[]{-1,-2,-3,2});
        // int result = new Problem41().firstMissingPositive(new int[]{-1,-2,-3});
        int result = new Problem41().firstMissingPositive(new int[]{1, 1});
        System.out.println(result);
    }

}
